package com.zklh.leetcode.top100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 随机链表复制
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/7
 */
public class Solution138 {

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        List<Node> newList = new ArrayList<>();
        Map<Node, Node> oldNodeToNewNode = new HashMap<>();
        Node current = head;
        Node preHead = new Node(0);
        Node preNewCurrent = preHead;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.random = current.random;
            preNewCurrent.next = newNode;
            oldNodeToNewNode.put(current, newNode);
            preNewCurrent = newNode;
            current = current.next;
        }

        current = preHead.next;
        while (current != null) {
            if (current.random == null) {
                current = current.next;
                continue;
            }
            Node oldNode = current.random;
            current.random = oldNodeToNewNode.get(oldNode);
            current = current.next;
        }

        return preHead.next;
    }
}